package org.hegang.algorithm.mergesort;

import org.hegang.algorithm.common.RandomNumber;

import java.util.Arrays;

/**
 * @ClassName Merge
 * @Describe: 归并排序
 * @Author: gang.he
 * @Email: SmileSkylife@outlook.com
 * @Date: Created in 20:05 2020/4/29
 * @Modified_By:
 * @Version: V1.0
 */
public class MergeSort {


    public static void mergeSort(int[] arrays, int left, int right, int[] tmp) {
        if (arrays == null || arrays.length == 0) {
            return;
        }
        // 采用递归方式, 如果left小于right，代表还没有分完，继续拆分，直到只剩下一个元素
        if (left < right) {
            int mid = (left + right) / 2;
            // 拆分为左组，直到拆到只有一个元素
            mergeSort(arrays, left, mid, tmp);
            // 拆分为右组, 直到拆到只有一个元素
            mergeSort(arrays, mid + 1, right, tmp);
            // 归并: 拆分完后真正的归并排序
            merge(arrays, left, mid, right, tmp);
        }
    }

    private static void merge(int[] arrays, int left, int mid, int right, int[] tmp) {
        // 定义左子组第一个未排序的坐标
        int l_pos = left;
        // 定义右子组第一个未排序的坐标, mid被划分为左子组，因此右子组第一个坐标是[mid+1]
        int r_pos = mid + 1;
        // 定义临时数组的坐标
        int tmp_pos = left;
        // 比较左子组和右子树第一个未排序的元素
        while (l_pos <= mid && r_pos <= right) {
            // 当左子组第一个元素比右子组第一个元素小时，把左子组元素塞入临时数组
            // 并且左子组坐标加一，代表第一个元素已排序
            // 同时临时数组坐标加一，其接收下一个元素。
            if (arrays[l_pos] < arrays[r_pos]) {
                tmp[tmp_pos++] = arrays[l_pos++];
            } else {
                tmp[tmp_pos++] = arrays[r_pos++];
            }
        }

        // 当出现两边子组不一致，比如奇数个元素，左右子组元素肯定不一致，这时候直接把已经有序元素的拷贝进临时数组即可
        while (l_pos <= mid) {
            tmp[tmp_pos++] = arrays[l_pos++];
        }
        while (r_pos <= right) {
            tmp[tmp_pos++] = arrays[r_pos++];
        }

        // 临时数组已经排好序，这时候把临时数组的元素拷贝回原数组arrays即可
        while (left <= right) {
            arrays[left] = tmp[left++];
        }
    }

    public static void main(String[] args) {
        RandomNumber randomNumber = new RandomNumber();
        int[] arrays = randomNumber.generateRandomNumberByRandom(0, 100, 30);
        System.out.println("排序前：" + Arrays.toString(arrays));
        int[] tmp = new int[arrays.length];
        mergeSort(arrays, 0, arrays.length - 1, tmp);
        // 归并排序
        System.out.println("排序后：" + Arrays.toString(arrays));
    }
}
